//给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
// 
//
// 示例 1： 
//
// 
//输入：nums = [10,5,2,6], k = 100
//输出：8
//解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
//需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,2,3], k = 0
//输出：0 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 3 * 104 
// 1 <= nums[i] <= 1000 
// 0 <= k <= 106 
// 
// Related Topics 数组 滑动窗口 
// 👍 423 👎 0

package com.cute.leetcode.editor.cn;
public class SubarrayProductLessThanK {
    public static void main(String[] args) {
        int[] nums = {10,5,2,6};
        new SubarrayProductLessThanK().new Solution().numSubarrayProductLessThanK(nums, 0);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 滑动窗口
        public int numSubarrayProductLessThanK(int[] nums, int k) {
            if (k <= 1) return 0;// 根据条件判断直接返回了
            int res = 0;
            int len = nums.length;
            for (int r = 0, l = 0, cur = 1; r < len; r++){
                cur *= nums[r];
                while (cur >= k) cur /= nums[l++];
                /**
                 * 右边界增加之后需要增加新的连续子数组的数量
                 * 例如原来指到[1,2]此时的子数组为[1][1,2][2]
                 * 添加3之后为[1,2,3]此时新增的子数组为[1,2,3][2,3][3]，新增的个数为right - left + 1
                 */
                res += r - l + 1;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}